«
»

Heap (maxheap) implementation

March 17, 2012, 12:05 am

A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

class Heap {

public:

  Heap() {
    store.push_back(0);
  }

  int l_child(int idx) {
    return idx*2;
  }

  int r_child(int idx) {
    return (idx*2)+1;
  }

  int get_parent(int idx) {
    return (idx/2);
  }

  void insert(int val) {
    store.push_back(val);

    int idx = store.size()-1;

    if(idx == 1) return;

    // bubble up
    for(;store[get_parent(idx)] < store[idx];) {
      int t = store[get_parent(idx)];
      store[get_parent(idx)] = val;
      store[idx] = t;
      idx = get_parent(idx);
      if(get_parent(idx) == 0) break;
    }
  }

  void dump() {
    cout << "DUMPSTART" << endl;
    for(size_t n=0;n<store.size();n++) {
      cout << store[n] << endl;
    }
    cout << "DUMPEND" << endl;
  }

  int pop() {
    int r = store[1];

    store[1] = store[store.size()-1];
    store.pop_back();

    bool min=true;
    int idx = 1;
    for(;min==true;) {

      min=false;

      int lidx = l_child(idx);
      int ridx = r_child(idx);
 
      int lval;
      int rval;
      if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;
      if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;

      if(store[idx] < lval) { min=true; }
      if(store[idx] < rval) { min=true; }

      if(!min) break;

      int t = store[idx];
      if(lval > rval) {
        store[idx] = store[l_child(idx)];
        store[l_child(idx)] = t;
        idx = l_child(idx);
      } else {
        store[idx] = store[r_child(idx)];
        store[r_child(idx)] = t;
        idx = r_child(idx);
      }
    }
    return r;
  }

  vector<int> store;
};

int main() {

  vector<int> testdata;

  for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);

  Heap myheap;
  for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);

  cout << "popping heap:" << endl;
  for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;

  cout << "sorted testdata:" << endl;
  sort(testdata.rbegin(),testdata.rend());
  for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;
 
  cout << "second test: " << endl;
  Heap myheap2; 
  for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);
  for(size_t n=0;n<(testdata.size()/2);n++) cout << myheap2.pop() << endl;
  myheap2.insert(100);
  myheap2.insert(7);
  for(size_t n=0;n<(testdata.size()/2)+2;n++) cout << myheap2.pop() << endl;

}
Category: Uncategorized  |  Comment (RSS)  |  Trackback